#include"DynamicArray.h"
#include<iostream>
#include<cmath>
#include<limits.h>

DynamicArray::DynamicArray(size_t capacity):size(0),capacity(capacity)
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    this->freeptr = a.freeptr;
    this->EqualPtr = a.EqualPtr;
    this->PrintPtr = a.PrintPtr;
    this->SortPtr = a.SortPtr;
    for(int i = 0; i < size; i ++)
    {
        array[i] = a.array[i];
    }
}

DynamicArray& DynamicArray::operator=(const DynamicArray &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    this->freeptr = a.freeptr;
    this->EqualPtr = a.EqualPtr;
    this->PrintPtr = a.PrintPtr;
    this->SortPtr = a.SortPtr;
    for(int i = 0; i < size; i ++)
    {
        array[i] = a.array[i];
    }
    return *this;
}

void DynamicArray::show()
{
    for(int i = 0; i < size; i ++)
    {
        PrintPtr(array[i]);
    }
    std::cout << std::endl;
}

size_t DynamicArray::Size()
{
    return size;
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = (size > capacity) ? capacity : size;

    ElementType *newP = new ElementType[capacity];
    for(size_t i = 0; i < size; i ++)
    {
        newP[i] = array[i];
    }
    delete[] array;
    array = newP;
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if(size >= capacity)
        ReSize(2 * capacity);
    
    array[size++] = element;
}

void DynamicArray::InsertHead(const ElementType &element)
{
    if(size >= capacity)
        ReSize(2 * capacity);
    for(size_t i = size; i > 0; i --)
    {
        array[i] = array[i - 1];
    }
    freeptr(array[0]);
    array[0] = element;
    size ++;
}

void DynamicArray::InsertByIndex(int index, const ElementType &element)
{
    if(index < 0 || index > size)
    {
        return;
    }
    if(size >= capacity)
        ReSize(2 * capacity);
    for(size_t i = size; i > index; i --)
    {
        array[i] = array[i - 1];
    }
    freeptr(array[index]);
    array[index] = element;
    size ++;
}

void DynamicArray::RemoveByIndex(int index)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    freeptr(array[index]);
    for(size_t i = index; i < size - 1; i ++)
    {
        array[i] = array[i + 1];
    }
    size --;
}

void DynamicArray::RemoveByElement(const ElementType &element)
{
    for(int i = 0; i < size; i ++)
    {
        if(EqualPtr(element, array[i]) == 0)
        {
            RemoveByIndex(i);
            i --;
        }
    }
}

ElementType* DynamicArray::FindByIndex(int index)
{
    if(index < 0 || index >= size)
        return nullptr;
    return &array[index];
}

DynamicArray DynamicArray::FindByElement(const ElementType &element)
{
    DynamicArray d;
    for(int i = 0; i < size; i ++)
    {
        if(EqualPtr(element, array[i]) == 0)
        {
            d.InsertTail(new int(i));
        }
    }
    return d;
}

void DynamicArray::showIndex()
{
    for(int i = 0; i < size; i ++)
    {
        int* j = (int*)array[i];
        std::cout << *j << std::endl;
    }
}

void DynamicArray::UpdateByIndex(int index, const ElementType &element)
{
    if(index < 0 || index >= size)
        return;
    freeptr(array[index]);
    array[index] = element;
}

void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    for(int i = 0; i < size; i ++)
    {
        if(EqualPtr(array[i], oldValue) == 0)
        {
            freeptr(array[i]);
            array[i] = newValue;
        }
    }
}

void DynamicArray::Sort()
{
    FastSort(0,size - 1, 0, 2 * log2(size));
    // InsertSort(0,size - 1);
}

void DynamicArray::Duplicate()
{
    for(int i = 1; i < size; i ++)
    {
        if(EqualPtr(array[i], array[i - 1]) == 0)
        {
            RemoveByIndex(i);
            i --;
        }
    }
}

DynamicArray DynamicArray::Merge(const DynamicArray& a)
{
    size_t first = 0;
    size_t second = 0;
    DynamicArray result;

    while(first < this->size && second < a.size)
        if(SortPtr(array[first],a.array[second]) < 0)
            result.InsertTail(array[first++]);
        else
            result.InsertTail(a.array[second++]);

    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);

    return result;
}

DynamicArray DynamicArray::FdInterScth(const DynamicArray &a)
{
    DynamicArray result;
    // for(int i = 0; i < size; i ++)
    // {
    //     for(int j = 0; j < a.size; j ++)
    //     {
    //         if(array[i] == a.array[j])
    //         {
    //             result.InsertTail(array[i]);
    //         }
    //     }
    // }

    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(EqualPtr(array[first], a.array[second]) == 0)
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(SortPtr(array[first], a.array[second]) > 0)
        {
            second ++;
        }
        else
        {
            first ++;
        }
    }
    return result;
}

DynamicArray DynamicArray::FdUnionSet(const DynamicArray &a)
{
    DynamicArray result;
    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(EqualPtr(array[first], a.array[second]) == 0)
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(SortPtr(array[first], a.array[second]) > 0)
        {
            result.InsertTail(a.array[second ++]);
        }
        else
        {
            result.InsertTail(array[first ++]);
        }
        
    }

    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);

    return result;
}

DynamicArray DynamicArray::FdDifference(const DynamicArray &a)
{
    DynamicArray result;
    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(EqualPtr(array[first], a.array[second]) == 0)
        {
            first++;
            second++;
        }
        else if(SortPtr(array[first], a.array[second]) > 0)
        {
            result.InsertTail(a.array[second ++]);
        }
        else
        {
            result.InsertTail(array[first ++]);
        }
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

DynamicArray DynamicArray::subsequence(int index, size_t size)
{
    if(index < 0 || index + size > this->size)
        return DynamicArray();
    DynamicArray result;
    result.EqualPtr = EqualPtr;
    result.freeptr = freeptr;
    result.PrintPtr = PrintPtr;
    result.SortPtr = SortPtr;
    for(int i = index; i < index + size; i ++)
    {
        result.InsertTail(array[i]);
    }
    return result;
}

bool DynamicArray::operator==(const DynamicArray &a)
{
    if(size != a.size) return false;
    for(int i = 0; i < size; i ++)
    {
        if(EqualPtr(array[i], a.array[i]) == 1)
            return false;
    }
    return true;
}

size_t DynamicArray::BinarySearch(const ElementType &element)
{
    size_t left = 0;
    size_t right = size;
    while(left <= right)
    {
        size_t mid = (left & right) + (left ^ right) >> 1;
        if(EqualPtr(element,array[mid]) == 0)
            return mid;
        else if(SortPtr(array[mid], element) > 0)
        {
            if(mid == 0)
                return ULONG_MAX;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return ULONG_MAX;
}

bool DynamicArray::IsChild(const DynamicArray &a)
{
    // for(int i = 0; i < a.size; i ++)
    // {
    //     if(FindByElement(a.array[i]).size == 0)
    //     {
    //         return false;
    //     }
    // }
    // return true;
    int j = 0;
    for(int i = 0; i < size; i ++)
    {
        if(array[i] == a.array[j])
        {
            j ++;
        }
    }
    return j == a.size;
}

//滑动窗口
bool DynamicArray::IsCntnsChils(const DynamicArray &a)
{
    // int flag = 1;
    // int j = 0;
    // for(int i = 0; i < size; i ++)
    // {
    //     if(flag == 0)
    //     {
    //         if(j == a.size) return true;
    //         j = 0;
    //         flag = 0;
    //     }
    //     if(array[i] == a.array[j])
    //     {
    //         j ++;
    //         flag = 1;
    //     }
    //     else
    //     {
    //         flag = 0;
    //     }
    // }
    // if(j == a.size) return true;
    // return false;

    for(int i = 0; i <= size - a.size; i ++)
    {
        if(subsequence(i,a.size) == a)
        {
            return true;
        }
    }
    return false;
}

void DynamicArray::SetFreePtr(void (*freeptr)(ElementType))
{
    this->freeptr = freeptr;
}

void DynamicArray::SetPrintPtr(void (*PrintPtr)(ElementType))
{
    this->PrintPtr = PrintPtr;
}

void DynamicArray::SetSortPtr(int (*SortPtr)(ElementType, ElementType))
{
    this->SortPtr = SortPtr;
}

void DynamicArray::SetEqualPtr(bool (*EqualPtr)(ElementType, ElementType))
{
    this->EqualPtr = EqualPtr; 
}

void DynamicArray::FastSort(size_t start, size_t end, size_t deepth, size_t MaxDeepth)
{
    if(start >= end) return;
    
    if(deepth > MaxDeepth)
    {
        InsertSort(start, end);
    }
    else
    {
        size_t par = Partition(start, end);
        if(par != 0)
            FastSort(start, par - 1, deepth + 1, MaxDeepth);
        FastSort(par + 1, end, deepth + 1, MaxDeepth);
    }
}

void DynamicArray::InsertSort(size_t start, size_t end)
{
    for(size_t i = 0; i <= end; i ++)
    {
        size_t j = i;
        ElementType temp = array[j];
        for(; j > start; j --)
        {
            if(SortPtr(array[j - 1], temp) > 0)
            {
                array[j] = array[j - 1];
            }
            else
            {
                break;
            }
        }
        array[j] = temp;
    }
}

size_t DynamicArray::Partition(size_t start, size_t end)
{
    if(start >= end) return 0;
    size_t left = start;
    size_t right = end;
    ElementType temp = array[left];
    while(left < right)
    {
        while(SortPtr(array[right], temp) > 0 && left < right)
            right --;
        if(left < right)
            array[left ++] = array[right];
        while(SortPtr(array[left], temp) < 0 && left < right)
            left ++;
        if(left < right)
            array[right --] = array[left];
    }
    array[left] = temp;
    
    return left;
}

DynamicArray::~DynamicArray()
{
    delete[] array;
}